package dp;

import java.util.HashMap;
import java.util.List;

//拿牌问题改动态规划
public class TakeCards {
    //两个人都按照最优规划拿牌 只能拿最左或者最右 最终会有一个获胜者  先后拿都有可能获胜
    //最优规划：先拿的 要保证当前情况下拿完之后 再经过后手拿后 自己扔可以从剩余的里面获得最大
    //        后拿的，要保证当前情况下，对手拿完后，自己再拿后 给对手剩下的是最小
    //递归
    public static void main(String[] args) {
        int[] arr = {5, 35, 1, 6};
        System.out.println(win1(arr));
    }

    public static int win1(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        System.out.println(firstT(arr, 0, arr.length - 1));
        System.out.println(lastT(arr, 0, arr.length - 1));
        return 0;
    }

    //先手拿获得的最优节
    public static int firstT(int[] arr, int L, int R) {
        //只有两种情况 1，只剩一张牌  拿走就好    2、两张及以上的时候，选择拿走左边和右边中加起来可以获得最优解的拿个
        if (L == R) {
            return arr[L];
        }
        return Math.max(arr[L] + lastT(arr, L + 1, R), arr[R] + lastT(arr, L, R - 1));
    }

    //定义一个黑盒 在L - R上，某人后手可以获得的最优解
    public static int lastT(int[] arr, int L, int R) {
        if (L == R) {
            return 0;
        }
        return Math.min(firstT(arr, L + 1, R), firstT(arr, L, R - 1));
    }


}
